package _dp_base;

/**
 * 714. 买卖股票的最佳时机含手续费
 */
public class No714 {
    private int[] prices;
    private int fee;

    /**
     * 1. 递归
     */
    public int maxProfit1(int[] prices, int fee) {
        this.prices = prices;
        this.fee = fee;
        int n = prices.length;

        return dfs(n - 1, 0);
    }

    private int dfs(int i, int hold) {
        if (i < 0) return hold == 0 ? 0 : Integer.MIN_VALUE / 2;
        else if (hold == 0) return Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i] - fee);
        else return Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);
    }

    /**
     * 2. 迭代
     */
    public int maxProfit2(int[] prices, int fee) {
        int n = prices.length;

        int[][] f = new int[n + 1][2];
        f[0][1] = Integer.MIN_VALUE / 2;
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = Math.max(f[i][0], f[i][1] + prices[i] - fee);
            f[i + 1][1] = Math.max(f[i][1], f[i][0] - prices[i]);
        }

        return f[n][0];
    }

    /**
     * 4. 空间优化
     */
    public int maxProfit4(int[] prices, int fee) {
        int[] f = new int[2];
        f[1] = Integer.MIN_VALUE / 2;
        for (int price : prices) {
            int temp = Math.max(f[0], f[1] + price - fee);
            f[1] = Math.max(f[1], f[0] - price);
            f[0] = temp;
        }

        return f[0];
    }
}
